#! /usr/bin/env python
# -*- coding: utf-8 -*-

from bisect import insort, bisect_right, bisect_left
import copy
def overflow(foo):
        def _overflow(self, *args, **kwargs):
                if len(self)>=self._maxlen:
                        raise IndexError('Interval is overflow')
                return foo(self, *args, **kwargs)
        return _overflow

def index_insort(lst, key):
        lo = 0
        hi = len(lst)
        ln = hi
        while lo < hi:
                mid = (lo+hi)/2
                if lst[mid].getmax()[0] < key:
                        lo = mid+1
                else:
                        hi = mid
        if lo >= ln: lo = ln-1
        return lo


class interval(list):
        def __init__(self, maxlen):
                self._maxlen = maxlen

        def __str__(self):
                return str(self + \
                                ['' for i in xrange(self._maxlen \
                                                - len(self))])
        @overflow
        def append(self, obj):
                insort(self, obj)
                    
        #@overflow
        def extend(self, obj):
                if len(self)+len(obj)>self._maxlen:
                        raise IndexError('Interval is overflow')
                list.extend(self, obj)

        def getmax(self):
                return self[-1]
        
        def search(self, key):
                lst = []
                res = True
                i = bisect_left(self, key)
                ln = len(self)
                while i<ln and res == True:
                        if self[i][0] == key:
                                lst.append(self[i])
                        if self[i][0] > key:
                                res = False
                        i = i+1
                        
                #for x in self:
                #        if x[0] == key:
                #                lst.append(x)
                #        if x[0] > key:
                #                res = False
                return (res, lst)

class area_iter():
        def __init__(self, area):
                self._area = area
                i = 0
                while ((area.indexes[i] == '') or (i in area.indexes.values())):
                        i = i + 1
                self._index = i
                
        def next(self):
                if self._index != 'e':
                        res = (self._index, self._area._lst[self._index])
                        self._index = self._area.indexes[self._index]
                else:
                        raise StopIteration
                return res
                
                
class area:
        def __init__(self, maxlen):
               self._maxlen = maxlen
               self.indexes = dict((x, '') for x in xrange(self._maxlen))
               self._lst = [[] for i in xrange(maxlen)]
               
        def __str__(self):
                res = str(self.indexes) + '\n\n'
                for el in self._lst:
                        res += str(el) + '\n'
                return res
        
        def __iter__(self):
                return area_iter(self)
                
        def __setitem__(self, key, value):
                self._lst[key] = value
                
        def __getitem__(self, key):
               return self._lst[key]

        def append(self, obj):
                for i, x in self:
                        if x.getmax()>=obj:
                                break
                try:
                        self._lst[i].append(obj)
                except IndexError:
                        self.split_interval(i)
                        self.append(obj)
                                
               
        def split_interval(self, index):
                _freeInt = self._getNearestFreeInt(index)
                _lenIntrvl = self._lst[index]._maxlen
                _intrvl = interval(_lenIntrvl)
                _intrvl.extend(self._lst[index][(_lenIntrvl+1)/2:])
                self._lst[index][(_lenIntrvl+1)/2:] = []
                self._lst[_freeInt] = _intrvl
                self.indexes[_freeInt] = self.indexes[index]
                self.indexes[index] = _freeInt

        def _getNearestFreeInt(self, index):
                lst_free = [key for key, value in \
                        self.indexes.iteritems() if value == '']
                if len(lst_free) == 0:
                        raise IndexError('Area is overflow')
                return lst_free[bisect_right(lst_free, index)%len(lst_free)]

        def getmax(self):
                for key, value in self.indexes.iteritems():
                        if value == 'e':
                                return self._lst[key].getmax()

        def normalize(self, maxlenintrvl):
                for i in xrange(self._maxlen):
                        if self.indexes[i] == '':
                                self._lst[i] = interval(maxlenintrvl)
                        
        def search(self, key):
                lst = []
                res = True
                for i, x in self:
                        if x.getmax() >= key:
                                res, lst_tmp = x.search(key)
                                lst.extend(lst_tmp)
                                if res == False:
                                        return res, lst
                return res, lst
                
class vsam:
        def __init__(self):
                self._lst = []
        
        def __setitem__(self, key, value):
                self._lst.insert(key, value)
        
        def __getitem__(self, key):
                return self._lst[key]

        def __len__(self):
                return len(self._lst)
        
        def __str__(self):
                res = '\n'
                for x in self._lst:
                        res = res + str(x)+'\n'
                return res

        def split_area(self, index):
                _lenArea = self._lst[index]._maxlen
                #создаем 2 области
                _area1 = area(_lenArea)
                _area2 = area(_lenArea)
                #проходим по переполненной и заполняем
                count = 0
                for i, _int in self._lst[index]:
                        if count < _lenArea/2:
                                _area1[i] = _int
                                _area1.indexes[i] = self._lst[index].indexes[i]
                                end_of_ar1 = i
                        else:
                                _area2[i] = _int
                                _area2.indexes[i] = self._lst[index].indexes[i]
                        count = count + 1
                _area1.indexes[end_of_ar1] = 'e'       
                # заменяем
                _area1.normalize(_int._maxlen)
                _area2.normalize(_int._maxlen)
                self._lst[index] = _area1
                self._lst.insert(index+1, _area2)
                
        def append(self, obj):
                i = index_insort(self._lst, obj[0])
                try:
                        self._lst[i].append(obj)
                except IndexError:
                        self.split_area(i)
                        self.append(obj)
                return i

        def search(self, key):
                lst = []
                res = True
                i = index_insort(self._lst, key)
                while (res != False):
                        res, lst_tmp = self._lst[i].search(key)
                        lst.extend(lst_tmp)
                        i = i+1
                return lst

class intervalCreator:
        def __init__(self, filename, lenIntrvl):
                self._file = open(filename,'r')
                self._lenIntrvl = lenIntrvl
                self._stop = False
                
        def __iter__(self):
                return self
        
        def next(self):
                if self._stop == True:
                        raise StopIteration
                _lst = []
                for i in xrange(self._lenIntrvl):
                        line = self._file.readline()
                        if not line:
                                self._stop = True
                                self._file.close()
                                if len(_lst) == 0:
                                        raise StopIteration
                                return _lst
                        word = line.split()
                        _lst.append( ( int(word[1]), word[0]) )
                return _lst
        
class areaCreator:
        def __init__(self, filename, IntrvlCount=12, IntrvlSize=8,\
                     freefract=0.25, freeIntrvls=[4,8,12]):
                self.IC = intervalCreator(filename,int(IntrvlSize*(1-freefract)))
                self._count = IntrvlCount
                self._freeIntrvls = freeIntrvls
                self._IntrvlSize = IntrvlSize
                self._stop = False
        
        def __iter__(self):
                return self
        
        def next(self):
                if self._stop == True:
                        raise StopIteration
                _area = area(self._count)
                _intrvl = interval(self._IntrvlSize)
                _intrvl.extend(self.IC.next())
                _area[0] = _intrvl
                prev = 0
                
                for i in xrange(1,self._count):
                        try:
                                _intrvl = interval(self._IntrvlSize)
                                if i+1 in self._freeIntrvls:
                                        _area[i] = _intrvl
                                        _area.indexes[i] = ''
                                else:
                                        _intrvl.extend(self.IC.next())
                                        _area[i] = _intrvl
                                        _area.indexes[prev] = i
                                        prev = i
                        except StopIteration:
                                _area[i] = _intrvl
                                _area.indexes[i] = ''
                                self._stop = True
                _area.indexes[prev] = 'e'
                return _area

def createVsam(filename):
        db = vsam()
        for i,x in enumerate(areaCreator(filename)):
                db[i] = x
        return db

db = createVsam('./my_file.txt')
